 #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int check[7];
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);
        return ret;
    }

    void dfs(vector<int>& nums)
    {
        if (path.size() == nums.size())
        {
            ret.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            if (!check[i])
            {
                check[i] = true;
                path.push_back(nums[i]);

                //继续递归后面的数
                dfs(nums);

                //回溯，恢复现场
                check[i] = false;
                path.pop_back();
            }
        }
    }
};

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;

    vector<vector<int>> subsets(vector<int>& nums) {
        if (nums.empty()) return ret;
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos)
    {
        ret.push_back(path);
        for (int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
        return;
    }
};

class Solution {
public:
    int sum = 0;
    int path = 0;

    int subsetXORSum(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        dfs(nums, 0);
        return sum;
    }

    void dfs(vector<int>& nums, int pos)
    {
        sum += path;
        for (int i = pos; i < nums.size(); i++)
        {
            path ^= nums[i];
            dfs(nums, i + 1);
            path ^= nums[i];
        }

        return;
    }
};

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[9];

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos)
    {
        // if(path.size() == nums.size())
        // {
        //     ret.push_back(path);
        //     return;
        // }

        // for(int i = 0; i < nums.size(); i++)
        // {
        //     // //只关心"不合法"分支
        //     // if(check[i] || (i != 0 && nums[i - 1] == nums[i] && check[i - 1]))
        //     //     continue;

        //     // check[i] = true;

        //     // //直接将这个点添加进path
        //     // path.push_back(nums[i]);
        //     // dfs(nums);

        //     // //回溯
        //     // path.pop_back();
        //     // check[i] = false;

        //     //只关心"合法"分支
        //     if(!check[i] && (i == 0 || nums[i - 1] != nums[i] || !check[i - 1] == true))
        //     {
        //         check[i] = true;
        //         //添加该位置
        //         path.push_back(nums[i]);
        //         dfs(nums);

        //         //回溯
        //         path.pop_back();
        //         check[i] = false;
        //     }
        //     else
        //         continue;
        // }
        // return;


        //优化一部分
        if (pos == nums.size())
        {
            ret.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            // //只关心"不合法"分支
            // if(check[i] || (i != 0 && nums[i - 1] == nums[i] && check[i - 1]))
            //     continue;

            // check[i] = true;

            // //直接将这个点添加进path
            // path.push_back(nums[i]);
            // dfs(nums, pos + 1);

            // //回溯
            // path.pop_back();
            // check[i] = false;

            //只关心"合法"分支
            if (!check[i] && (i == 0 || nums[i - 1] != nums[i] || !check[i - 1] == true))
            {
                check[i] = true;
                //添加该位置
                path.push_back(nums[i]);
                dfs(nums, pos + 1);

                //回溯
                path.pop_back();
                check[i] = false;
            }
            else
                continue;
        }
        return;
    }
};